package com.code.leetcode._202508;

//64 最小路径和
public class MinPathSum {
    /**
     * 给定一个包含非负整数的m*n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小
     * 说明：每次只能向下或者向右移动一步
     * 示例1：输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
     * 输出：7
     * 解释：因为路径 1→3→1→1→1 的总和最小
     * 示例2：输入：grid = [[1,2,3],[4,5,6]]
     * 输出：12
     **/
    public static void main(String[] args) {
        MinPathSum m = new MinPathSum();
        System.out.println(m.minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
    }

    /**
     * 动态规划
     * 由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素
     * 只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。
     * 对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应
     * 的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值，
     * 由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。
     * 创建二维数组dp，与原始网格的大小相同，dp[i][j]表示从左上角出发到(i,j)位置的最小路径和。显然，dp[0][0]=grid[0][0]
     * 对于dp中的其余元素，通过以下状态转移方程计算元素值。
     * 1、当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。
     * 2、当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。
     * 3、当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。
     * 最后得到dp[m-1][n-1]的值即为网格左上角到网格右下角的最小路径和
     ***/
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }

}
